{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## algorithm design and anlysis-2025 spring  homework 1 \n",
    "**Deadline**：2025.5.14\n",
    "\n",
    "**name**:\n",
    "\n",
    "\n",
    "note：\n",
    "---\n",
    "1. 带有\\*的题目，申请免上课的同学，必须完成，其他同学选作；\n",
    "2. 请独立完成，如求助了他人或者大模型，请著明，并且不可省略算法分析部分；\n",
    "4. 如若作答有雷同，全部取消成绩；\n",
    "3. 需要书面作答的题目，可以通过引用图片的形式添加，但是注意上传项目时包含所引用的图片的源文件；\n",
    "4. $log_n$ 默认表示$log_2{n}$;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题 1\n",
    "\n",
    "对于下面的每一对表达式(A, B), A是否能表示为B的 $\\Theta, \\Omega ,O$形式. 请注意, 这些关系中的零个、一个或多个可能成立。列出所有正确的。经常发生一些学生会,把指示写错, 所以请把关系写完整, 例如: $A = O(B),  A =\\Theta(B)$, 或$A = \\Omega(B)$。\n",
    "\n",
    "1. $A=n^2-100n, B=n^2$\n",
    "2. $A=logn, B=log_{1.2}n$\n",
    "3. $A=3^{2n}, B=2^{4n}$\n",
    "4. $A=2^{logn}, B=n$\n",
    "5. $A=\\log{\\log}{n},B=10^{10^{100}}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "can refer a handwritten picture, pleas upload the picture in /fig/xxx.png\n",
    "answer:\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题 2：\n",
    "\n",
    "假设有函数 $f$ 和 $g$ 使得 $f(n)$ = $O(g(n))$ 对于下面的每一个陈述, 请判断对错, 如果正确请给出证明, 否则请给出一个反例。\n",
    "\n",
    "1. $\\log{f(n)}$ = $O(\\log(1+g(n)))$\n",
    "2. $3^{f(n)}=O(3^{g(n)})$\n",
    "3. $(f(n))^2=O((g(n))^2)$ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "you can refer a handwritten picture, pleas upload the picture in /fig/xxx.png\n",
    "answer:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题 3\n",
    "\n",
    "根据下列递归公式, 计算下列 $T(n)$ 对应的的渐近上界。要求所求的边界尽可能的紧（tight）, 请写明步骤。\n",
    "\n",
    "1. $T(1)=1; T(n)=T(n/4)+1$ for $n>1$\n",
    "2. $T(1)=1;T(n)=3T(n/3)+n^2$ for $n>1$\n",
    "3. $T(1)=1;T(n)=T(2n/3)+1$ for $n>1$\n",
    "4. $T(1)=1;T(n)=5T(n/4)+n$ for $n>1$\n",
    "5. $T(n)=1 \\ for\\ n \\le 2 ; T(n)=T(\\sqrt{n})+1 \\ for \\ n>2$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "can refer a handwritten picture, pleas upload the picture in /fig/xxx.png\n",
    "answer:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题 4：\n",
    "\n",
    "给定一个包含n个元素的数组 `profits` , 它的第 `i` 个元素 `profits[i]` 表示一支股票第 `i` 天的**收益**（正数表示涨, 负数表示跌）。你只能选择 **某一天** 买入这只股票, 并选择在 **未来的某一个不同的日子** 卖出该股票。\n",
    "\n",
    "1. 设计一个算法来计算你所能获取的最大利润和对应买入和卖出的日期。请分析算法方案, 计算其时间复杂度, 并且使用python编程实现该算法。\n",
    "\n",
    "2. \\* 设计一个时间复杂度为 $O(n)$的算法实现该算法\n",
    "\n",
    "e.g. :\n",
    "---\n",
    "profits=[3,2,1,-7,5,2,-1,3,-1], 第5天买入, 第8天卖出, 收益最大：9\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "idea:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# add your code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# an algorithm with O(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题 5：\n",
    "\n",
    "观察下方的分治算法（divide-and-conquer algorithm）的伪代码, 回答下面问题\n",
    "\n",
    "```latex\n",
    "DoSomething(A,p,r)\n",
    "-----\n",
    "n := r-p+1\n",
    "if n=2 and A[p]>A[r] then\n",
    "    swap A[p] and A[r]\n",
    "else if n >= 3 then\n",
    "    m = ceil(2n/3)\n",
    "    DoSomething(A,p,p+m-1)\n",
    "    DoSomething(A,r-m+1,r)\n",
    "    DoSomething(A,p,p+m-1)  \n",
    "    \n",
    "---\n",
    "first call: DoSomething(A,1,n)\n",
    "```\n",
    "\n",
    "note：$ceil(2n/3)=\\left\\lceil {2n/3} \\right\\rceil$；$:=$ 表示赋值, 等价于 $\\to$；A是一个包含n的整数元素的数组, \n",
    "\n",
    "1. 写出该算法时间复杂度的递归公式, 并求解其对应的渐进表示\n",
    "2. 描述一下该算法的功能, 并判断是否是最高效的解决方案\n",
    "3. 使用python编程实现上述算法或其对应的更高效版本的算法\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "idea："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "answer:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# add your code here\n",
    "# your algorithm time complexity is :"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题 6：\n",
    "\n",
    "给定一个大小为 `n` 的数组 `nums` , 返回其中的多数元素。多数元素是指在数组中出现次数 **大于** `⌊ n/2 ⌋` 的元素。\n",
    "\n",
    "你可以假设数组是非空的, 并且给定的数组总是存在多数元素。\n",
    "\n",
    "1. 设计一个算法找到给定数组的多数元素, 分析算法设计思路, 计算算法时间复杂度, 使用python编程实现\n",
    "2. \\* 设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题, 分析算法设计思路, 使用python编程实现\n",
    "\n",
    "e.g.:\n",
    "---\n",
    "1. nums=[3,2,3], 返回3\n",
    "2. nums=[2,2,1,1,1,2,2], 返回2\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "idea："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# add your code here\n",
    "# your algorithm time complexity is :"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "idea for 2\\*："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# algorithm time complexity：O(n), space complexity:O(1)\n",
    "# add your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题 7：\n",
    "\n",
    "给定一个包含不同整数元素的数组 $ A[1..n]$ ,并且满足条件：$A[1]>A[2]$ 并且 $A[n-1]<A[n]$; 规定：如果一个元素比它两边的邻居元素都小, 即：$A[x]<A[x-1], A[x]<A[x+1]$ , 称这个元素A[x]为“局部最小”。通过遍历一次数组, 我们可以很容易在 $O(n)$的时间复杂度下找到一个局部最小值, \n",
    "\n",
    "\n",
    "1. 分析该问题, 设计一个算法在$O(logn)$的时间复杂度下找到一个局部最小(返回数值), 要求：分析算法设计思路, 并且使用python编程实现\n",
    "2. \\* 设计算法找出所有局部最小值, 分析算法设计思路, 并使用python编程实现\n",
    "\n",
    "e.g.:\n",
    "---\n",
    "A=[9, 3, 7, 2, 1, 4, 5 ] 时,  局部最小元素为 3, 1\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "idea："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# add your code here\n",
    "# your algorithm time complexity is :"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "idea:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# add your code here\n",
    "# your algorithm time complexity is :"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题 8：\n",
    "\n",
    "给定包含n个不同数字的一组数, 寻找一种基于比较的算法在这组数中找到k个最小的数字, 并按顺序输出它们。\n",
    "\n",
    "1. 将n个数先进行排序, 然后按顺序输出最小的k个数。要求：选择合适的排序算法实现上述操作, 计算算法时间复杂度, 并使用python编程实现。\n",
    "2. 建立一个包含这n个数的堆（heap）, 并且调用 k 次Extract-min 按顺序输出最小的k个数。使用往空堆中不断插入元素的方法建立堆, 分析这种方法建堆的时间复杂度, 并使用python编程实现\n",
    "3. \\* 假设数组中包含的数据总数目超过了计算机的存储能力, 请设计一个算法, 找到这堆数据的前k小的数值, 计算时间复杂度, 并使用python实现该算法, 假设计算机一定能存储k个数据。\n",
    "\n",
    "e.g.：\n",
    "---\n",
    "数组arr=[5,4,3,2,6,1,88,33,22,107] 的前3个最小数据为：1, 2, 3\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "idea："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# add your code here\n",
    "# your algorithm time complexity is :"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题 9：\n",
    "\n",
    "**选择问题**:给定一个包含n个未排序值的数组A和一个$k≤n$的整数, 返回A中最小的第k项。\n",
    "\n",
    "在课堂上, 学了一个简单的O(n)随机算法来解决选择问题。事实上还有一种更复杂的最坏情况下时间复杂度为$O(n)$ 的选择算法。假设使用一个黑盒过程来实现这个O(n)选择算法: 给定一个数组A、 $p < r$ 和 k,  $BB(A, p, r, k)$ 可以在$O(r−p+ 1)$时间内找到并报告$A[p..r]$中第k小的项的下标。假设你可以在线性时间内处理Partition过程。\n",
    "\n",
    "1. 请分析如何修改 Quicksork 算法可以使其最差情况下的运行时间为 $O(nlogn)$, 使用伪代码实现, 并分析为何修改后的版本最差情况的运行时间为$O(nlogn)$\n",
    "\n",
    "note: 伪代码中, 你可以直接调用用` BB(A,p,r,k)`这个函数用于表示在最坏情况下时间复杂度为$O(n)$的选择算法；\n",
    "\n",
    "\n",
    "\n",
    "2. 找到一个更好的算法报告数组A中的前k小的项, 使用伪代码表示你的算法, 并分析你算法的时间复杂度。\n",
    "\n",
    "举例：A=[13, 3, 7, 9, 11, 1, 15, 2, 8, 10, 12, 16, 14, 5], 当k=4时, 应该报告1, 2, 3, 4\n",
    "\n",
    "note： 最直观的方法就是先将数组A排序, 然后从左向右报告其前k项, 这样操作的时间复杂度为$O(nlogn)$. 调用用` BB(A,p,r,k)`设计一个算法使其报告无序数组A的前k项, 满足时间复杂度好于$\\Theta(nlogn)$, 并且当$k=\\sqrt{n}$时, 你设计的算法时间复杂度应该为$\\Theta(n)$.\n",
    "\n",
    "\n",
    "\n",
    "3. 给定一个大小为n的数组, 找到一个 时间复杂度为$O(n log k)$ 的算法, 该算法将A中的元素重新排序, 使它们被划分为k个部分, 每个部分的元素小于或等于下一部分的元素。假设n和k都是2的幂。使用伪代码表示你的算法, 并分析时间复杂度。\n",
    "\n",
    "e.g.:\n",
    "---\n",
    "数组：[1,  3,  5,  7,  9,  11,  13,  15,  2,  4,  6,  8,  10,  12,  16,  14], k=4, \n",
    "\n",
    "对应重新排序的数组为：[1,  3,  2,  4]  [7,  6,  5,  8]  [12,  11,  10,  9]  [13,  14,  16,  15]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "idea："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# add your pseudo-code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题 10：\n",
    "\n",
    "给定一个包含m个**字符串**的数组A, 其中不同的字符串可能有不同的字符数, 但数组中所有字符串的字符总数为n。设计一个算法在 $O(n)$ 时间内对字符串进行排序, 分析算法设计方案, 计算其时间复杂度, 并基于python编程实现该算法。请注意, 假设字符串只包含\"a\",\"b\",...,\"z\", \n",
    "\n",
    "\n",
    "\n",
    "举例1：数组A=[\"a\", \"da\", \"bde\", \"ab\", \"bc\", \"abdc\", \"cdba\"], 排序后的数组应该为：['a', 'ab', 'abdc', 'bc', 'bde', 'cdba', 'da']\n",
    "\n",
    "\n",
    "\n",
    "举例2：数组A=['ab', 'a', 'b', 'abc', 'ba', 'c'], 排序后的数组应该为：\n",
    "\n",
    "['a', 'ab', 'abc', 'b', 'ba', 'c']\n",
    "\n",
    "\n",
    "\n",
    "举例3：数组A=['aef', 'yzr', 'wr', 'ab', 'bhjc', 'lkabdc', 'pwcdba'],  排序后的数组应该为：['ab', 'aef', 'bhjc', 'lkabdc', 'pwcdba', 'wr', 'yzr']\n",
    "\n",
    "\n",
    "\n",
    "note：\n",
    "\n",
    "-  两个字符之间的比较可以考虑比较他们对应的ASCII码值；\n",
    "- python中可以使用`ord(\"a\")`返回字符 “a”对应的ASCII值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "idea:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# add your code here\n",
    "# your algorithm time complexity is :"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
